/**
 * A List[T] is an immutable singly linked list.
 */
enum List[T] {
    Cons(head: T, tail: Ptr[List[T]]);
    Empty;

    // /**
    //  * Returns a new list which combines two other lists. Requires iterating
    //  * over both lists, which is O(n).
    //  */
    // public function concat(other: Self): Self {
    //     var list = Empty;
    //     for i in this {
    //         list = i :: list;
    //     }
    //     for i in other {
    //         list = i :: list;
    //     }
    //     return list.reverse();
    // }

    /**
     * Returns a new list, with the provided value added to the front of this
     * list.
     */
    public function cons(value: T): Self {
        return Cons(value, &this);
    }

    // public function pushBack(value: T): Self {
    //     return this.reverse().cons(value).reverse();
    // }

    // /**
    //  * Return a new list, which is this list in reverse order. Requires O(n)
    //  * time. This does not modify the current list.
    //  */
    // public function reverse(): Self {
    //     var list = Empty;
    //     for i in this {
    //         list = i.cons(list);
    //     }
    //     return list;
    // }

    /**
     * Return the length of the list. Requires O(n) to calculate.
     */
    public function getLength(): Size {
        var len = 0;
        var current = this;
        while true {
            match current {
                Cons(h, t) => {
                    ++len;
                    current = *t;
                }
                default => break;
            }
        }
        return len;
    }

    public function isEmpty(): Bool {
        match this {
            Cons(_, _) => return false;
            default => return true;
        }
    }

    public function contains(value: T): Bool {
        match this {
            Cons(h, t) => {
                if h == value {
                    return true;
                } else {
                    return t.contains(value);
                }
            }
            default => return false;
        }
    }

    // public function head(): T {
    //     match this {
    //         Cons(h, _) => return h;
    //     }
    // }

    // public function tail(): List[T] {
    //     match this {
    //         Cons(_, t) => return t;
    //     }
    // }

    rules {
        ($this.length) => $this.getLength();

        // /**
        //  * Returns the first element of this list if the list is not empty, or None
        //  * otherwise.
        //  */
        // (this.head) => match this {
        //     Cons(h, t) => Some(h);
        //     Empty => None;
        // }

        // /**
        //  * Returns the list without its first element. If the list is already empty,
        //  * returns an empty list.
        //  */
        // (this.tail) => match this {
        //     Cons(h, t) => t;
        //     Empty => Empty;
        // }

        // /**
        //  * Check whether the list is empty in constant time.
        //  */
        // (this.empty) => match this {
        //     Empty => true;
        //     default => false;
        // }

        // ((it: Iterable[T]) as Self) => {
        //     var list = Empty;
        //     for i in it {
        //         list = i :: list;
        //     }
        //     list.reverse();
        // }

        // /**
        //  * Use the cons operator to construct a list out of individual values:
        //  *
        //  *     var myList = 1 :: 2 :: 3 :: Empty;
        //  *
        //  * The cons operator is right associative, so this parses as:
        //  *
        //  *     var mList = 1 :: (2 :: (3 :: Empty));
        //  */
        // ((head: T)::(tail: Self)) => Cons(head, tail);

        // optimize List iteration at compile time when the type is known
        (for $ident in $this {$e}) => {
            var __rest = $this;
            do {
                match __rest {
                    Cons($ident, t) => {
                        {$e}
                        __rest = t;
                    }
                    default => {
                        break;
                    }
                }
            } while true;
        }
    }
}

// implement(T) Iterable(T) for List[T] {
//     public function iterator() {
//         return this;
//     }
// }

// implement(T) Iterator[T] for List[T] {
//     public function next(): (Box[Iterator[T]], Option[T]) {
//         match list {
//             Cons(h, t) => {
//                 return (*t, Some(h));
//             }
//             default => {
//              return (this, None);
//             }
//         }
//     }
// }
